package done.normal_001_100;

import com.study.common.ListNode;
import org.junit.Test;

import static com.study.util.LogUtil.info;

/**
 * 19. Remove Nth Node From End of List 删除链表的倒数第N个节点
 * <p>
 * 给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
 * <p>
 * 示例：
 * 给定一个链表: 1->2->3->4->5, 和 n = 2.
 * 当删除了倒数第二个节点后，链表变为 1->2->3->5.
 * <p>
 * 2019-05-18 14:00
 **/
@SuppressWarnings("all")
public class RemoveNthNodeFromEndOfList {

    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 190519 first
        return null;
    }

    @Test
    public void test() {
        info(removeNthFromEnd(new ListNode(1, 2, 3, 4, 5), 2));
    }
}






















































/*
// 一、两次遍历方法
public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    int len  = 0;
    ListNode first = head;
    while (first != null) {
        len++;
        first = first.next;
    }

    len = len - n;
    ListNode cur = dummy;
    while (len > 0) {
        len--;
        cur = cur.next;
    }

    cur.next = cur.next.next;
    return dummy.next;
}

// 二、一次遍历法, 快慢指针法
public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode first = dummy;
    ListNode second = dummy;
    for (int i = 1; i <= n + 1; i++) {
        first = first.next;
    }

    while (first != null) {
        first = first.next;
        second = second.next;
    }
    second.next = second.next.next;
    return dummy.next;
}
*/